Many different types and styles of semiconductor memory devices exist to store data for electronic devices such as computers, portable media players, and digital cameras. For example, dynamic random access memory (DRAM) and static random access memory (SRAM) are two types of volatile memory. Programmable read only memory, electrically erasable programmable read only memory (EEPROM), and flash memory are three common types of nonvolatile memory. Flash memory is nonvolatile computer memory that can be electrically erased and reprogrammed. Because flash memory costs far less than many of the various nonvolatile memory technologies, designers tend to use flash memory elements in systems wherever significant amounts of nonvolatile, solid-state storage is needed.
Two types of flash memory are NOR-based flash memory and NAND-based flash memory. NOR flash memory elements generally have long erase and/or write times, but have the advantage of allowing random access to individual memory locations. NAND flash memory uses tunnel injection for writing and tunnel release for erasing. NAND flash memory devices are common in such technology sectors as removable universal serial bus (USB) storage devices and many types of memory cards, such as memory cards for digital cameras, digital video recorders, and portable music players.
NAND memory technologies typically require an embedded processor to perform a logical-to-physical (LTP) translation. The LTP translation presents memory storage in a linear, block-oriented, view to system software or an operating system. The LTP translation is usually necessary due to numerous NAND memory requirements, such as the need to erase before writing, performing wear leveling to maximize device life, and handling bad blocks and other media issues. Systems generally implement LTP translation via an LTP array in system memory. The LTP array maps the logical address presented to the system to a physical NAND block as stored on the memory device. For example, a typical case of one 32 bit table entry for each 4 kilobyte (KB) NAND page, the LTP array size may be 1 megabyte (MB) for each 1 gigabyte (GB) of NAND memory. Implementing LTP array maps in system memory are generally used for host-based systems, where access to system dynamic random access memory (DRAM) may be fast and relatively efficient.
Some systems, such as embedded systems, reduce the need for accesses to LTP arrays by using a technique referred to as “Delta Tables”. The Delta Table method uses a tree structure of ‘deltas’ to describe fragmented areas of the memory device, where data stored on the device is fragmented or scattered around physical memory locations of the device. This mechanism may work well in some situations, but is inefficient for workloads having a large number of small writes, such as when a system uses the memory device as a write-back cache. Additionally, the Delta Table method frequently requires large amounts of memory to contain the delta tables.